package ru.susu.algebra;

import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.Arrays;

/**
 * @author akargapolov
 * @since: 10.12.2009
 */
public class PartitionNumberCounter
{
	private static int size = 1001;

	private static BigInteger data[][] = new BigInteger[size][size];

	public static void main(String[] args)
	{
		fillSquareMatrix();
		// viewSquareMatrix();

		// viewOddEvenLengthDifferents();
		//partsFormula();

		for (int i = 1;i<=100;i++)
		{
			System.out.println(i + ": " + data[size - 1][i]);
			//System.out.println(i + ": " + data[i][i]);
		}
	}

	private static void fillSquareMatrix()
	{
		for (int i = 0; i < size; i++)
		{
			Arrays.fill(data[i], BigInteger.ZERO);
		}

		data[0][0] = BigInteger.ONE;
		for (int i = 1; i < size; i++)
		{
			for (int j = 1; j <= i; j++)
			{
				//all partitions
				//data[i][j] = data[i][j - 1].add(data[i - j][Math.min(i - j, j)]);
				//different
				data[i][j] = data[i][j - 1].add(data[i - j][Math.min(i - j, j - 1)]);
			}
		}
	}

	private static void viewSquareMatrix()
	{
		for (int i = 1; i < size; i++)
		{
			System.out.println(i + " = " + data[i][i]);
		}
	}

	private static void viewOddEvenLengthDifferents()
	{
		for (int i = 2; i < size; i++)
		{
			BigInteger one = BigInteger.ZERO, second = BigInteger.ZERO;
			for (int j = 1; j <= i; j++)
			{
				if (j % 2 == 0)
				{
					one = one.add(data[i][j]);
				}
				else
				{
					second = second.add(data[i][j]);
				}
			}
			System.out.println(one + "\n" + second + "\n");
		}
	}

	private static void partsFormula()
	{
		int i = size - 1;
		for (int j = 1; j <= i; j++)
		{
			System.out.println(j + ":\n" + data[i][j] + "\n" + getPartsNumber(i, j));
		}
	}

	private static BigDecimal getPartsNumber(int n, int k)
	{
		BigDecimal result = BigDecimal.valueOf(n).pow(k - 1);
		for (int j = 1; j <= k - 1; j++)
		{
			BigDecimal v = BigDecimal.valueOf(j);
			result = safeDivide(safeDivide(result, v), v);
		}
		result = safeDivide(result, BigDecimal.valueOf(k));
		return result;
	}

	private static BigDecimal safeDivide(BigDecimal v1, BigDecimal v2)
	{
		BigDecimal remainder = v1.remainder(v2);
		return v1.subtract(remainder).divide(v2);
	}
}
